package com.algrithom.sort;

import com.util.CommonUtil;

class MergeSort {
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{6,2,1,3,7,9,10,1};
        mergeSort(array);
    }
    
    /**
     * 归并排序
     *
     * @param array 数组
     */
    public static void mergeSort(Integer[] array){
        Integer[] result = new Integer[array.length];
        recursiveMergeSort(array,result,0,array.length - 1);
    }
    
    /**
     * 递归的归并排序
     *
     * @param workSpace 辅助排序的数组
     * @param lowerBound 欲归并数组段的最小下标
     * @param upperBound 欲归并数组段的最大下标
     */
    private static void recursiveMergeSort(Integer[] workSpace,Integer[] result,int lowerBound,int upperBound){
        if (lowerBound != upperBound) {
            int mid = (lowerBound + upperBound) / 2;
            // 对低位段归并排序
            recursiveMergeSort(workSpace,result,lowerBound,mid);
            // 对高位段归并排序
            recursiveMergeSort(workSpace,result,mid + 1,upperBound);
            merge(workSpace,result,lowerBound,mid,upperBound);
            CommonUtil.display(workSpace);
        }
    }
    
    /**
     * 对数组array中的两段进行合并，lowerBound~mid为低位段，mid+1~upperBound为高位段
     *
     * @param workSpace 辅助归并的数组，容纳归并后的元素
     * @param lowerBound 合并段的起始下标
     * @param mid 合并段的中点下标
     * @param upperBound 合并段的结束下标
     */
    private static void merge(Integer[] workSpace,Integer[] result,int lowerBound,int mid,int upperBound){
        // 低位段的起始下标
        int lowBegin = lowerBound;
        int highBegin = mid + 1;
        int j = 0;
        // 归并的元素总数
        int n = upperBound - lowerBound + 1;
        
        while (lowBegin <= mid && highBegin <= upperBound) {
            // 将两者较小的那个放到workSpace中
            if (workSpace[lowBegin] < workSpace[highBegin]) {
                result[j++] = workSpace[lowBegin++];
            } else {
                result[j++] = workSpace[highBegin++];
            }
        }
        
        while (lowBegin <= mid) {
            result[j++] = workSpace[lowBegin++];
        }
        
        while (highBegin <= upperBound) {
            result[j++] = workSpace[highBegin++];
        }
        // 将归并好的元素复制到array中
        for (j = 0; j < n; j++) {
            workSpace[lowerBound++] = result[j];
        }
    }
}
